package com.xigua._树;

import com.xigua.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给你一棵二叉搜索树的 root ，请你 按中序遍历 将其重新排列为一棵递增顺序搜索树，
 * 使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。
 *
 *
 * @date 2022/4/213:08
 */
public class _897_递增顺序搜索树 {

    List<Integer> ans = new ArrayList<>();
    public TreeNode increasingBST(TreeNode  root) {
        dfs(root);
        TreeNode result = new TreeNode(ans.get(0));
        TreeNode p = result;
        for (int i = 1; i < ans.size(); i++) {
            p.right = new TreeNode(ans.get(i));
            p = p.right;
        }
        return result;
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        ans.add(root.val);
        dfs(root.right);
    }


}
